package leetcode.code0363;

import java.util.TreeSet;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * int[][] block = new int[n * m >> 1][n + 1]; <BR>
 * 存在负数答案，ans初始化0就错了 <BR>
 * ans找Max，ans的初始值得是Min <BR>
 */
public class Solution3 implements IDebug {

	public int maxSumSubmatrix(int[][] matrix, int k) {
		int m = matrix.length;
		int n = matrix[0].length;
		int[][] sums = new int[m + 1][n + 1];
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				sums[i][j] = sums[i - 1][j] + matrix[i - 1][j - 1];
			}
		}
		int[][] block = new int[(m * (m + 1) >> 1) + 1][n + 1];
		int b = 0;
		for (int i = 0; i < m; i++) {
			for (int j = i + 1; j <= m; j++) {
				for (int c = 1; c <= n; c++) {
					block[b][c] = sums[j][c] - sums[i][c];
				}
				b++;
			}
		}
		int ans = Integer.MIN_VALUE;
		int[] temp = new int[n + 1];
		for (int i = 0; i < b; i++) {
			TreeSet<Integer> tm = new TreeSet<>();
			tm.add(0);
			for (int j = 1; j <= n; j++) {
				int cur = temp[j - 1] + block[i][j];
				temp[j] = cur;
				Integer ceil = tm.ceiling(cur - k);
				if (ceil != null) {
					int close2k = cur - ceil;
					ans = Math.max(ans, close2k);
					if (ans == k) {// 不return Java 57.08%
						return k;
					}
				}
				tm.add(cur);
			}
		}
		return ans == Integer.MIN_VALUE ? -1 : ans;
	}

	@Override
	public void debug1() {
		HelpDebug.compare(2, this.maxSumSubmatrix(HelpDebug.str2array1("[[1,0,1],[0,-2,3]]"), 2));

	}

	@Override
	public void debug2() {
		HelpDebug.compare(3, this.maxSumSubmatrix(HelpDebug.str2array1("[[2,2,-1]]"), 3));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub
		HelpDebug.compare(-2, this.maxSumSubmatrix(HelpDebug.str2array1("[[5,-4,-3,4],[-3,-4,4,5],[5,1,5,-4]]"), -2));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution3 so = new Solution3();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
